import java.util.Arrays;

public class Demo01 {
    public static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag=true;
                }
            }
            if(!flag){
                return;
            }
        }
    }


    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        if(end-start+1<=14){
            insertSort2(array,start,end);
            return;
        }
        int index=midThree(array,start,end);
        swap(array,index,start);

        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static void insertSort2(int[] array,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=left ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    private static int midThree(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            } else if (array[mid]>array[right]) {
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[right]){
                return right;
            }else if(array[mid]>array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }
    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left< right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left< right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] arr1={12,33,1,5,8,55,88,2};
        bubbleSort(arr1);
        System.out.println("冒泡排序：");
        System.out.println(Arrays.toString(arr1));
        int[] arr2={44,4,5,55,7,8,1};
        bubbleSort(arr2);
        System.out.println("冒泡排序：");
        System.out.println(Arrays.toString(arr2));
    }
}
